Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\smid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\deriv}{\partial} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\network}{N} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \newcommand{\tauPmin}{\tau_{p_\min}} \)
\color{black}s \color{black}t
(edge-based) dynamic flow $f=(f^+_e,f^-_e)$ in dyn. flow network $N=(G,s,t,\nu,\tau)$ with capacities $\nu_e \gt 0$ and travel times $\tau_e \geq 0$:
\color{#3333FF}f^+_e: \IR \to \IRnn \color{#3333FF}f^-_e: \IR \to \IRnn v w \color{gray}\tau_e \color{gray}\nu_e
with cumulative in-/outflow $F^\pm_e(\theta) \coloneqq \int_0^\theta f^\pm_e(\zeta)\diff\zeta$,     value up to $T$: $\fval{f,T} \coloneqq \sum_{e \in \edgesTo{t}}F^-_e(T) - \sum_{e \in \edgesFrom{t}}F^+_e(T)$
  • respects capacities if $f^-_e(\theta) \leq \nu_e$ for almost all $\theta \in \IR$, $e \in E$
  • weak flow conservation at nodes if $\sum_{e \in \edgesFrom{v}}F^+_e(\theta) \class{tempstep}{\data{tempstep-classes=8:hl}{\leq}} \sum_{e \in \edgesTo{v}}F^-_e(\theta)$ for all $\theta \in \IR$, $v \neq s,t$
    weak flow conservation at nodes and $\fval{f,\theta} \class{tempstep}{\data{tempstep-classes=8:hl}{\geq 0}}$ for all $\theta \in \IR$
  • weak flow conservation on edges if $F^-_e(\theta+\tau_e) \class{tempstep}{\data{tempstep-classes=10:hl}{\leq}} F^+_e(\theta)$ for almost all $\theta \in \IR$, $e \in E$
  • strong flow conservation at nodes if $\sum_{e \in \edgesFrom{v}}F^+_e(\theta) \class{tempstep}{\data{tempstep-classes=8:hl}{=}} \sum_{e \in \edgesTo{v}}F^-_e(\theta)$ for all $\theta \in \IR$, $v \neq s,t$
    weak flow conservation at nodes and $\fval{f,\theta}$ non-decreasing
  • strong flow conservation on edges if $F^-_e(\theta+\tau_e) \class{tempstep}{\data{tempstep-classes=10:hl}{=}} F^+_e(\theta)$ for almost all $\theta \in \IR$, $e \in E$
feasible
direct
dynamic flow
path-based dynamic flow $(f_p: \IR \to \IRnn)_{p \in \PathSet}$ mmm ⤳ corresponding direct dynamic flow $(f_e^+,f^-_e)$ defined by:
\[f^+_e\class{tempstep a}{\data{tempstep-from=16}{(\theta)}} \coloneqq \sum\nolimits_{p \in \PathSet: e \in p}f^+_p\class{tempstep a}{\data{tempstep-from=16}{(\theta-\tau_{p|_{\lt e}})}} \class{tempstep a}{\data{tempstep-from=17}{\quad\text{and}\quad f^-_e(\theta) \coloneqq f^+_e(\theta-\tau_e)}}.\]
feas. $(f^+_e,f^-_e)$ is maximum dynamic flow with time horizon $T$ $\coloniff$ $\forall$ feas. dyn. flows $(g^+_e,g^-_e): \fval{g,T} \leq \fval{f,T}$
Theorem 3.10:
For any dynamic flow network $N=(G,s,t,\nu,\tau)$ and $T \in \IRnn$
there exists a maximum dynamic flow with time horizon $T$.
Extreme Value Theorem:
$K$ non-empty, compact, $\Phi: K \to \IR$ continuous
$\implies$ $\exists x^* \in K: \Phi(x^*) = \sup\Set{\Phi(x) \SMid x \in K}$
\color{black}s \color{black}t
$(x_e)$ static $s$,$t$-flow in $(G,s,t,\nu)$ with path-cycle-decomposition $(x_p)$
  → associated temporally repeated flow $f=(f^+_e)$ is direct dynamic flow corresponding to path-based dynamic flow \[f^+_p(\theta) \coloneqq \begin{cases}0, &\text{ if } \theta \lt 0 \\ x_p, &\text{ if } \theta \geq 0\end{cases}.\]
Lemma 3.12: $(x_e)$ feasible $s$,$t$-flow $\implies$ associated temp. rep. flow $f$ is feasible direct dynamic flow with
\[\fval{f,T} \geq T\cdot\fvals{x} - \sum_{e \in E}\tau_e x_e. \quad\quad (\#)\]
We have equality if $(x_e)$ has path-decomposition with $x_p=0$ for all $p \in \PathSet$ with $\tau_p \gt T$.
-T \color{black}s \color{black}t
Lemma 3.13: $(x'_e)$ mincost flow in $\network'$, $(x_e)$ its restriction to $\network$ and $(x_p)$ a path-cycle decomposition. Then
  • $x_p \gt 0 \implies \tau_p \leq T$
  • $x_c \gt 0 \implies \tau_c = 0$
  • $(x_e)$ maximizes $T\cdot\fvals{x} - \sum_{e \in E}\tau_e x_e \quad\quad (\#)$
    Dynamic Ford-Fulkerson-Algorithm:
Input: $s$,$t$-network $\network=(G,s,t,\nu,\tau)$, time horizon $T$
Output: maximum dynamic flow $(f^+_e,f^-_e)$ with until $T$
  1. Construct $\network'$ from $\network$ by adding edge $ts$ with $\tau_{ts}=-T$ and $\nu_{ts}=\infty$
  2. Compute min-cost flow $x'$ of value $0$ in $\network'$ (with $\tau_e$ as cost)
  3. Determine path-cycle decomposition $(x'_p)$ of restriction of $x'$ to $\network$
  4. Return: Temporally repeated flow $f$ associated with $(x_p)$
dynamic $s$,$t$-cut with time horizon $T$: $(\beta_v) \in \IR^V$ with $\beta_s=0$, $\beta_t \geq T$ mmmm $v$ on $t$-side before $\beta_v$, on $s$-side after $\beta_v$
feas. dyn. flow $f$ is quickest flow with value $v$ if $\exists T \geq 0: \fval{g,\theta} \lt v = \fval{f,T}$ f.a. $\theta \in [0,T)$ and feas. dyn. flows $g$.
    Quickest Flow Algorithm:
Input: $s$,$t$-network $\network=(G,s,t,\nu,\tau)$, value $v$
Output: quickest flow $(f^+_e,f^-_e)$ with value $v$
  1. Repeat
  2. .. Guess time horizon $T$
  3. .. Compute maximum dynamic flow $f$ until $T$
  4. Until $\fval{f,T}=v$
Lemma 3.21: For any fixed network $\network$ the function
\[V: \IRnn \to \IRnn, T \mapsto \max\Set{\fval{f,T} \SMid \begin{array}{l}f \text{ a feas. dyn.}\\\text{flow in } \network\end{array}}\] is zero on $[0,\tauPmin]$ and strictly increasing on $(\tauPmin,\infty)$.
\color{black}(2,2) \color{black}(2,2) \color{black}(2,2) \color{black}(1,6) \color{black}(1,6) \color{black}s \color{black}t \color{black}v \color{black}w \color{black}\small \theta \color{black}\small \mathrm{value} \color{black}\small 4 \color{black}\small 8 \color{black}\small 12 \color{black}\small 16 \color{black}\small 6 \color{black}\small 8 \color{black}\small 10 \color{black}\small 12
    Earliest-Arrival Algorithm:
Input: dynamic flow network $\network=(G,s,t,\nu,\tau)$, time horizon $T$
Output: earliest arrival flow $f$ with time horizon $T$
  1. compute min-cost flow $y$ with ass. max. dyn. flow until $T$
  2. comp. min-cost flow $(x_p) \in \IRnn^{\PathSet^\leftrightarrow}$ of val. $\fvals{y}$ in $(G,s,t,\tau)$ by SSP
  3. def. gen. path-based dyn. flow $(f^+_p)$ by $f^+_p(\theta) \coloneqq x_p$ f.a. $\theta \geq 0$
  4. Return dynamic pseudo-flow coresponding to $(f^+_p)$
Dynamic Network Flows (SoSe 26), Chapter 3: Optimal Dynamic Flows
Lukas Graf (lukas.graf@uni-passau.de)
↑ All Slides